// POJ1895 Bring Them There
// 刘汝佳
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int maxn = 5000 + 10;
const int INF = 1e9;
struct Edge {
  int from, to, cap, flow;
};
bool operator<(const Edge& a, const Edge& b) {
  return a.from < b.from || (a.from == b.from && a.to < b.to);
}

struct Dinic {
  int n, m, s, t;
  vector<Edge> edges;  // 边数的两倍
  vector<int> G[maxn];  // 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号
  bool vis[maxn];  // BFS使用
  int d[maxn];     // 从起点到i的距离
  int cur[maxn];   // 当前弧指针

  void init() { edges.clear(); }

  void clearNodes(int a, int b) {
    for (int i = a; i <= b; i++) G[i].clear();
  }

  void AddEdge(int from, int to, int cap) {
    edges.push_back((Edge) {from, to, cap, 0});
    edges.push_back((Edge) {to, from, 0, 0});
    m = edges.size();
    G[from].push_back(m - 2), G[to].push_back(m - 1);
  }

  bool BFS() {
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(s), vis[s] = true, d[s] = 0;
    while (!Q.empty()) {
      int x = Q.front();
      Q.pop();
      for (size_t i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if (!vis[e.to] && e.cap > e.flow)
          vis[e.to] = true, d[e.to] = d[x] + 1, Q.push(e.to);
      }
    }
    return vis[t];
  }

  int DFS(int x, int a) {
    if (x == t || a == 0) return a;
    int flow = 0, f;
    for (int& i = cur[x]; i < G[x].size(); i++) {
      Edge& e = edges[G[x][i]];
      if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
        e.flow += f, edges[G[x][i] ^ 1].flow -= f;
        flow += f, a -= f;
        if (a == 0) break;
      }
    }
    return flow;
  }

  // 求s-t最大流。如果最大流超过limit，则只找一个流量为limit的流
  int Maxflow(int s, int t, int limit) {
    this->s = s, this->t = t;
    int flow = 0;
    while (BFS()) {
      memset(cur, 0, sizeof(cur));
      flow += DFS(s, limit - flow);
      if (flow == limit) break;  // 达到流量限制，直接退出
    }
    return flow;
  }
};

Dinic g;

const int maxm = 200 + 10;
int main() {
  int u[maxm], v[maxm];  // 输入边
  for (int n, m, k, S, T; scanf("%d%d%d%d%d", &n, &m, &k, &S, &T) == 5;) {
    for (int i = 0; i < m; i++) scanf("%d%d", &u[i], &v[i]);
    g.init();
    int day = 1;
    g.clearNodes(0, n - 1);  //第一层点为0~n-1。day层(day>=1):day*n~day*n+n-1
    int flow = 0;
    for (;;) {  // 判断day天是否有解
      // 一架飞船最多需要n-1天到达目的地，沿着这一路线最多需要n+k-2天
      // 就可以运完所有飞船，总结点数不超过(n+k-1)n
      g.clearNodes(day * n, day * n + n - 1);
      for (int i = 0; i < n; i++)
        g.AddEdge((day - 1) * n + i, day * n + i, INF);  // 原地不动
      for (int i = 0; i < m; i++) {
        g.AddEdge((day - 1) * n + u[i] - 1, day * n + v[i] - 1, 1); // u[i]->v[i]
        g.AddEdge((day - 1) * n + v[i] - 1, day * n + u[i] - 1, 1); // v[i]->u[i]
      }
      flow += g.Maxflow(S - 1, day * n + T - 1, k - flow);
      if (flow == k) break;
      day++;
    }

    // 输出解
    printf("%d\n", day);
    int idx = 0;
    vector<int> location(k, S);  // 每架飞船的当前位置
    for (int d = 1; d <= day; d++) {
      idx += n * 2;
      vector<int> moved(k, 0);  // 第d天有没有移动飞船i
      vector<int> a, b;         // 第d天有一架飞船从a[i]到b[i]
      for (int i = 0; i < m; i++) {
        int f1 = g.edges[idx].flow;
        idx += 2;
        int f2 = g.edges[idx].flow;
        idx += 2;
        if (f1 == 1 && f2 == 0) a.push_back(u[i]), b.push_back(v[i]);
        if (f1 == 0 && f2 == 1) a.push_back(v[i]), b.push_back(u[i]);
      }
      printf("%d", a.size());
      for (int i = 0; i < a.size(); i++) {
        // 查找是哪架飞船从a[i]移动到了b[i]
        for (int j = 0; j < k; j++)
          if (!moved[j] && location[j] == a[i]) {
            printf(" %d %d", j + 1, b[i]);
            moved[j] = 1, location[j] = b[i];
            break;
          }
      }
      printf("\n");
    }
  }
  return 0;
}
/*
算法分析请参考: 《入门经典训练指南-升级版》 5.6.4节 例题31
*/
// Accepted 1141ms 1868kB 3795 G++ 2020-12-14 18:48:38 22209628